package src.数据结构.栈;

public class Stack<T> {
    private Node head;
    private int N;

    public Stack() {
        this.head = null;
        this.N = 0;
    }

    public Stack(Node head, int n) {
        this.head = head;
        N = n;
    }

    public boolean isEmpty() {
        return this.N == 0;
    }

    public int size() {
        return this.N;
    }

    public void push(T t) {
        /* 第一轮                          第二轮                                 第三轮
         * 开始为空 直接插入 【顶】1           |                                    |
         * 非开始插入                        |  2,1                               |  3,2,1
         * 1. 找到 【顶】1                   | 1. 找到 【顶】2                      | 1. 找到 【顶】3
         * 2. 创建节点 2                    | 2. 创建节点 3                        | 2. 创建节点 4
         * 3. 将新节点 2 设置为栈顶【头节点】   | 3. 将新节点 3 设置为栈顶【头节点】      | 3. 将新节点 4 设置为栈顶【头节点】
         * 4. 让新节点 2 指向节点 1           | 4. 让新节点 3 指向节点 2              | 4. 让新节点 4 指向节点 3
         * 5. 序列 2,1                     | 5. 序列 3,2,1                       | 5. 序列 4,3,2,1
         * */
        // 找到首节点【栈顶】
        Node oldFirst = this.head;
        // 创建新节点
        Node<T> tNode = new Node<>(t, null);
        // 将新节点设置为首节点【栈顶】
        head = tNode;
        // 让新节点指向原来旧首节点
        tNode.next = oldFirst;
        this.N++;
    }

    public T pop() {
        // 找到栈顶【头节点】
        Node<T> top = this.head;
        if (top == null) {
            return null;
        }
        // 让栈顶设置为头节点的下一个节点
        this.head = top.next;
        this.N--;
        return top.item;
    }

    public void show() {
        Node<T> n = head;
        while (n != null) {
            System.out.print(n.item + " ");
            n = n.next;
        }
        System.out.println();
    }
}
